/**
 * 给定数组A,可以换一个数，问LIS是多少
 * 首先有一个结论，操作以后LIS最多加1。
 * 令M是A的LIS，只需要对每个位置验证是否能修改的使M加一即可
 * for i in [1...M-1]:
 *     找到最靠前的位置p, 使得A[1...p]的LIS是i
 *     找到最靠后的位置q, 使得A[q...N]的LIS是M - i
 *     然后看 p + 1 < q and A[p] + 1 < A[q] 是否成立
 * 其中找p、q位置可以在SparseTable上做二分实现。需要实现求出以i结尾的LIS以及以i开头的LIS
 * 
 * 再对0和M做特判。即如果还没有到末尾就达到了M，则肯定能够使得M加一
 * 或者非开头位置开头的LIS就能达到M，显然也能加一。
 * 
 * O(NlogN)
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using llt = long long;
using vi = vector<int>;
using vll = vector<llt>;
using pii = pair<int, int>;
using pll = pair<llt, llt>;


struct SegTree{ // 线段树带延迟

using llt = long long;

int N;

using value_type = int;
vector<value_type> data; // 线段树

using lazy_type = llt;
vector<lazy_type> lazy; // 延迟标记

/// 从下往上计算信息，要变动
value_type _up_(const value_type & ls, const value_type & rs) {
    return max(ls, rs);
}



/// 初始化，清零，不用动
void init(int n) {
    data.assign((N = n) + 1 << 2, value_zero());
    // lazy.assign(n + 1 << 2, lazy_zero());
}

/// 这个函数不用动
void modify(int pos, const lazy_type & delta){
    _modify(1, 1, N, pos, delta);
}

/// 这个函数不用动
value_type query(int a, int b){
    return _query(1, 1, N, a, b);
}

/// 几乎不用动
value_type _query(int t, int s, int e, int a, int b) {
    if(a <= s and e <= b) {
        return data[t];
    }

    int mid = (s + e) >> 1;
    value_type ans = value_zero(); // 如果求最值，这里不能用zero
    if(a <= mid) ans = _up_(ans, _query(lson(t), s, mid, a, b));
    if(mid < b) ans = _up_(ans, _query(rson(t), mid + 1, e, a, b));
    return ans;
}

/// 几乎不用动
void _modify(int t, int s, int e, int pos, const lazy_type & delta) {
    if(s == e) {
        data[t] = delta;
        return;
    }

    int mid = (s + e) >> 1;
    if(pos <= mid) _modify(lson(t), s, mid, pos, delta);
    else _modify(rson(t), mid + 1, e, pos, delta);
    _pushUp(t);
    return;
}

/// 这个函数不用动
void _pushUp(int t) {
    data[t] = _up_(data[lson(t)], data[rson(t)]);
}

/// 辅助函数，视线段树信息类型而变动
static const value_type & value_zero() {
    static const value_type VALUE0 = 0;
    return VALUE0;
}

/// 这两个函数不用变动
static int lson(int x) {return x << 1;}
static int rson(int x) {return lson(x) | 1;}


};

template<typename IT = vector<int>::const_iterator>
struct SparseTable{

using T = pair<int, int>;
using vt = vector<T>; 
using vvt = vector<vt>;

SparseTable() = delete;

IT head;
vvt data;

/// 从s开始的n个数，作为原始数组，建立ST表，索引从0开始
/// 整个ST期间，原始数组的内容不能改变
SparseTable(IT begin, int n):head(begin){
    data.assign(n, vt());

    for(int i=0;i<n;++i) {
		data[i].reserve(22); // 200w用22即可
		data[i].emplace_back(i, i);
	}

	for(int j=1,t;(t=1<<j)<=n;++j){
        for(int i=0;i+t<=n;++i){
			const auto & prv = data[i][j-1];
			const auto & nxt = data[i+(t>>1)][j-1];

			auto first = *(begin + prv.first) <= *(begin + nxt.first) ? prv.first : nxt.first;
			auto second = *(begin + nxt.second) <= *(begin + prv.second) ? prv.second : nxt.second;

			data[i].emplace_back(first, second);
		} 
	}

	return;
}

/// 查询[s, e]区间的极小极大值所在的下标，即距离构造函数begin的偏移量
/// 索引从0开始
T query(int s, int e)const{
    int k = static_cast<int>(log2((double)(e - s + 1)));
	const auto & p1 = data[s][k];
	const auto & p2 = data[e-(1<<k)+1][k];
    return {
        *(head + p1.first) <= *(head + p2.first) ? p1.first : p2.first,
		*(head + p2.second) <= *(head + p1.second) ? p1.second : p2.second 
	};
}


};

int N;
vector<int> A;
vi W;
SegTree St;
int Limit;
vi Start, Tail;

int procLeft(const SparseTable<> & st, int val){
    int left = 0, right = N - 1, mid;
    do{
        mid = (left + right) >> 1;
        if(Tail[st.query(0, mid).second + 1] < val) left = mid + 1;
        else right = mid - 1;
    }while(left <= right);
    return left;
}

int procRight(const SparseTable<> & st, int val){
    int left = 0, right = N - 1, mid;
    do{
        mid = (left + right) >> 1;
        if(Start[st.query(mid, N - 1).second + 1] >= val) left = mid + 1;
        else right = mid - 1;
    }while(left <= right);
    return right;
}

int proc(){
#ifndef ONLINE_JUDGE
    cout << "D:" << endl;
    for(int i=1;i<=N;++i) cout << " " << Tail[i];
    cout << endl;
    for(int i=1;i<=N;++i) cout << " " << Start[i];
    cout << endl;
#endif


    SparseTable<> stTail(Tail.begin() + 1, N);
    SparseTable<> stStart(Start.begin() + 1, N);

    int n = Tail[stTail.query(0, N - 1).second + 1];
    assert(Start[stStart.query(0, N - 1).second + 1] == n);

    /// 先特判一下
    for(int i=1;i<N;++i)if(Tail[i] == n)return n + 1;
    for(int i=2;i<=N;++i)if(Start[i] == n) return n + 1;

    for(int i=1;i<n;++i){
        int left = procLeft(stTail, i) + 1;
        int right = procRight(stStart, n - i) + 1;
#ifndef ONLINE_JUDGE
        cout << "val = " << i << ": " << left << ", " << right << endl;
#endif
        if(left + 1 < right){
            if(0 == left or N + 1 == right or A[left] + 1 < A[right]){
                return n + 1;
            }
        }
    }
    return n;
}

void work(){
    cin >> N;
    A.assign(N + 1, {});
    W.emplace_back(0);
    for(int i=1;i<=N;++i) {
        cin >> A[i];
        W.emplace_back(A[i]);
        // W.emplace_back(i + 1);
    }

    sort(W.begin(), W.end());
    W.erase(unique(W.begin(), W.end()), W.end());
    Limit = W.size();

    St.init(Limit);
    Tail.assign(N + 1, 0);
    for(int i=1;i<=N;++i){
        auto t = lower_bound(W.begin(), W.end(), A[i]) - W.begin();
        auto d = 0;
        if(t > 1) d = St.query(1, t - 1);
        St.modify(t, Tail[i] = d + 1);
    }

    St.init(Limit);
    Start.assign(N + 1, 0);
    for(int i=N;i>=1;--i){
        auto t = lower_bound(W.begin(), W.end(), A[i]) - W.begin();
        auto d = 0;
        if(t < Limit) d = St.query(t + 1, Limit);
        St.modify(t, Start[i] = d + 1);
    }

    cout << proc() << endl;
    return;
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
    
    int nofkase = 1;
	// cin >> nofkase;
	while(nofkase--) work();
	return 0;
}